\section*{Methods}

%We present a formal and detailed analysis of the effects of using short seeds
%versus long seeds on speed, memory usage and error tolerance of different
%mappers in the ``Dilemma: Short Seeds or Long Seeds'' section (Appendix).
%Briefly, short seeds provide faster lookup, better memory efficiency and higher
%error tolerance, whereas long seeds provide fewer locations subjected to
%edit-distance calculation, i.e. less overall computation. Because the total
%number of edit-distance calculation of a mapper scales quadratically with the
%number of locations of each seed as shown in Equation~\ref{eq:map_cost_2} (Appendix),
%mappers using longer seed are much faster than mappers using short seeds.
%Nonetheless, with longer seeds, the total number of permutations quadruples and
%therefore the memory usage of the lookup table quadruples. Further, according to
%the Pigeonhole Principle, longer seeds reduce the number of nonoverlapping seeds to which a
%read may be divided, thus they reduce the overall error tolerance of the mapper.
%
%As we describe in the ``Dilemma" section (Appendix), only a few short seeds are
%{\it expensive} short seeds (defined as seeds having many locations). 
%Extending these expensive short seeds into longer seeds provide the
%best reduction in mapping cost (Equation~\ref{eq:map_cost_2}, defined as the
%average number of locations provided by a random seed from the genome) 
%per unit increase in memory usage. Based on this
%observation, we propose using different seed lengths in the lookup table for
%seeds with different frequencies to achieve maximum reduction of mapping cost
%with minimum increase in memory footprint. We call this concept ``heterogeneous
%seeds".

As we described in the ``Dilemma'' section, each seed contributes to the mapping
cost quadratically proportional to the number of its locations
(Equation~\ref{eq:map_cost_2}). As a result the few expensive seeds in the
lookup table may drastically hinder the speed of the mapper, which coincides
with their ubiquitous appearances in the genome. We observe that at seed length
12, the 1.08\% expensive seeds in the lookup table, which have more than 100
locations, account for 95.7\% of the total mapping cost of all the seeds. While
longer seeds reduces the mapping cost of the mapper, they also reduce the
memory-efficiency of the mapper as well as the error tolerance of the mapper.

Our goal in this paper is to design a mechanism that provides small mapping
cost while preserving high memory-efficiency and high error-tolerance.

With the above observation, we propose using different seed lengths for different
seeds, according to the frequencies (number of locations) of the seed in the
reference genome. In particular, we replace only the expensive short seeds with
longer cheaper seeds while preserving the original cheap short seeds as is.
Consequently, the seeds in the lookup table all become cheap seeds which have
similar numbers of locations but nonuniform lengths. We call these seeds
``Heterogeneous Seeds''. Since heterogeneous seeds only replace expensive short
seeds which account for only 1.08\% of the short seeds, while most short seeds
in the lookup table are unmodified, the added overhead of heterogeneous seeds
is very small compared to short seeds.

In the remainder of this paper, we first propose the ``Heterogeneous Lookup
Table", a data structure that enables heterogeneous seeds. We then discuss the
``Jigsaw Seeds" and ``Overlapping Seeds" which is a seed dividing method that
retains the same level of error tolerance of heterogeneous seed as with short
seeds.

\input{./sections/4_1.tex} \input{./sections/4_2.tex}
